The present invention relates generally to forward error correcting (FEC) methodology. The present invention relates more particularly to a method for decoding Reed-Solomon (RS) encoded data for correcting erasures and errors in a manner which is computationally efficient and which is suited for very large scale integrated circuit (VLSI) implementation.
As data storage densities and data transmission rates increase, the ability of hardware devices to correctly recognize binary data diminishes. Such binary data, which comprises a string of bits, i.e., zeros and ones, must be correctly recognized so as to facilitate the proper interpretation of the information represented thereby. That is, each individual zero and one needs to be interpreted reliably, so as to facilitate the accurate reconstruction of the stored and/or transmitted data represented thereby.
Such increased storage densities and transmission rates place a heavy burden upon the hardware utilized to recognize the state of individual bits. In contemporary storage devices, high storage densities dictate that the individual data bits be stored very close to one another. Further, in some data storage systems, the difference between the manner in which a one and a zero is stored in the media is not great enough to make the reading thereof as reliable as desired.
High data transmission rates imply either that the time allocated for each bit is substantially reduced, or that a modulation scheme is utilized wherein small differences in amplitude, frequency, and/or phase indicate a distinct sequence of bits, e.g., such as in multi-bit modulation. In either instance, the ability of hardware devices to accurately and reliably interpret such transmitted data is substantially reduced.
As those skilled in the art will appreciate, increasing data storage density and/or increasing data transmission speed inherently increases the bit error rate, i.e., the percentage of error bits contained in a message. It is desirable to be able to identify and correct data errors which occur during data storage and/or transmission operations. By being able to identify and correct such data errors, data may be stored more densely and/or transmitted more rapidly. Moreover, the ability to correct errors facilitates storage and transmission of data in environments with low signal to noise ratios. Thus, more noise can be tolerated within a storage and transmission medium.
Encoding is performed by an encoder before the data is transmitted (or stored). Once the transmitted data is received at the receiver end, a decoder decodes the data and corrects any correctable errors. Many encoders first break the message into a sequence of elementary blocks; next they substitute for each block a representative code, or signal, suitable for input to the channel. Such encoders are called block encoders. The operation of a block encoder may be described completely by a function or table showing, for each possible block, the code that represents it.
Error-correcting codes for binary channels that are constructed by algebraic techniques involving linear vector spaces or groups are called algebraic codes. Any binary code contains a number of code words which may be regarded as vectors C=(c1, c2, . . . , cn) of binary digits ci. The sum C+Cxe2x80x2 of two vectors may be defined to be the vector (c1+cxe2x80x21, . . . , cn+cxe2x80x2n) in which coordinates of C and Cxe2x80x2 are added in modulo 2.
Thus, the vector sum of any two code words is also a code word. Because of that, these codes are linear vector spaces and groups under vector addition. Their code words also belong to the n-dimensional space consisting of all 2n vectors of n binary coordinates. Consequently, the coordinates ci must satisfy certain linear homogeneous equations. The sums in such equations are performed in modulo 2. In general, any r linearly independent parity check equations in c1, . . . , cn determine a linear subspace of dimension k=nxe2x88x92r. The 2k vectors in this subspace are the code words of a linear code.
The r parity checks may be transformed into a form which simplifies the encoding. This transformation consists of solving the original parity check equations for some r of the coordinates ci as expressions in which only the remaining nxe2x88x92r coordinates appear as independent variables. The k=nxe2x88x92r independent variables are called message digits because the 2k values of these coordinates may be used to represent the letters of the message alphabet. The r dependent coordinates, called check digits, are then easily computed by circuits which perform modulo 2 multiplications and additions.
At the receiver the decoder can also do modulo 2 multiplications and additions to test if the received digits still satisfy the parity check equations. The set of parity check equations that fail is called the xe2x80x9csyndromexe2x80x9d because it contains the data that the decoder needs to diagnose the errors. The syndrome depends only on the error locations, not on which code word was sent. In general, a code can be used to correct e errors if each pair of distinct code words differ in at least 2e+1 of the n coordinates. For a linear code, that is equivalent to requiring the smallest number d of xe2x80x9conesxe2x80x9d among the coordinates of any code word [excepting the zero word (0, 0, . . . , 0)] to be 2e+1 or more. Under these conditions each pattern of 0, 1, . . . , exe2x88x921, or e errors produces a distinct syndrome; the decoder can then compute the error locations from the syndrome. This computation may offer some difficulty, but at least, it involves only 2e binary variables, representing the syndrome, instead of all n coordinates.
The well known RS encoding methodology provides an efficient means of error detection which also facilitates forward error correction, wherein a comparatively large number of data errors in stored and/or transmitted data can be corrected. RS encoding is particularly well suited for correcting burst errors, wherein a plurality of consecutive bits become corrupted. RS encoding is an algebraic block encoding and is based upon the arithmetic of finite fields. A basic definition of RS encoding states that encoding is performed by mapping from a vector space of M over a finite field K into a vector space of higher dimension over the same field. Essentially, this means that with a given character set, redundant characters are utilized to represent the original data in a manner which facilitates reconstruction of the original data when a number of the characters have become corrupted.
This may be better understood by visualizing RS code as specifying a polynomial which defines a smooth curve containing a large number of points. The polynomial and its associated curve represent the message. That is, points upon the curve are analogous to data points. A corrupted bit is analogous to a point that is not on the curve, and therefore is easily recognized as bad. It can thus be appreciated that a large number of such bad points may be present in such a curve without preventing accurate reconstruction of the proper curve (that is, the desired message). Of course, for this to be true, the curve must be defined by a larger number of points than are mathematically required to define the curve, so as to provide the necessary redundancy. If N is the number of elements in the character set of the RS code, then the RS encode is capable of correcting a maximum of t errors, as long as the message length is equal to Nxe2x88x922t.
Although the use of RS encoding provides substantial benefits by enhancing the reliability with which data may be stored or transmitted, the use of RS encoding according to contemporary practice possesses inherent deficiencies. These deficiencies are associated with the decoding of RS encoded data. It should be noted that in many applications, the encoding process is less critical than the decoding process. For example, since CDs are encoded only once, during the mastering process, and subsequently decoded many times by users, the encoding process can use slower, more complex and expensive technology. However, decoding must be performed rapidly to facilitate real-time use of the data, e.g., music, programs, etc., and must use devices which are cost competitive in the consumer electronics market. DVDs and Digital Televisions also extensively use RS decoding to correct any errors in the incoming signals. Additionally, DVDs use RS decoding to correct erasures in the incoming signals. Because of the high data rate in these applications, the rate and efficiency of RS decoding implementations become very crucial. More applications of the RS codes are described in S. B. Wicker and V. K. Bhargava, Reed-Solomon codes and their application, New York: IEEE Press, 1994, and C. Basile et al., xe2x80x9cThe U.S. HDTV standard the grand,xe2x80x9d IEEE Spectrum, vol. 32, pp. 36-45, April 1995 the contents of which are hereby incorporated by reference.
Decoding RS encoded data involves the calculation of an error locator polynomial and an error evaluator polynomial. The error locator polynomial provides information about the location of errors in the received vector. One of two methods is typically utilized to decode RS encoded data. The Berlekamp-Massey (BM) algorithm described in E. R. Berlekamp, Algebraic coding theory, New York: McGraw-Hill, 1968, the content of which is hereby incorporated by reference, is the best known technique for finding the error locator. The BM algorithm is capable of being implemented in a VLSI chip. However, the BM algorithm utilizes an inversion process which undesirably increases the complexity of such a VLSI design and which is computationally intensive, thereby undesirably decreasing the speed of decoding process. Also well known is the use of Euclid""s algorithm for the decoding of RS encoded data. However, Euclid""s algorithm utilizes a polynomial division methodology which is also computationally intensive. A simplified Euclidean algorithm is defined in T. K. Truong, W. L. Eastman, I. S. Reed, and I. S. Hsu, xe2x80x9cSimplified procedure for correcting both errors and erasures of Reed-Solomon code using Euclidean algorithm,xe2x80x9d Proc. Inst. Elect. Eng., vol. 135, pt. E, pp. 318-324, November 1988, the content of which is hereby incorporated by reference.
In view of the foregoing, it is desirable to provide a method for correcting both errors and erasures, in transmitted data stored in a computer memory, using RS encoding by simultaneously computing an errata locator polynomial and an errata evaluator polynomial without performing polynomial division, without computing the discrepancies, and without inversion; and without a separate computation of an erasure polynomial and the Forney syndrome. This results in a VLSI implementation that is both faster and simpler. It is also desirable to provide a simple multiplication and a simple inversion process for simple and fast VLSI implementations. In addition to decoding RS encoded data, the multiplication and inversion processes can be used for data communication, data encryption and decryption, data compression and decompression, and many other data transformation processes that use multiplication and/or inversion.
The present invention specifically addresses and alleviates the above mentioned deficiencies associated with the prior art. More particularly, the present invention comprises a highly efficient decoding method to correct both erasures and errors for RS codes, which takes the advantages of Euclidean algorithm and BM algorithm. The procedure for correcting both errors and erasures involves calculating an error-erasure locator polynomial and calculating an error-erasure evaluator polynomial. These polynomials are called errata evaluator and errata locator polynomial hereinafter, respectively.
The new decoding method computes the errata locator polynomial and the errata evaluator polynomial simultaneously without performing the polynomial divisions, and there is no need to compute the discrepancies and the field element inversions. Also, separate computations of the erasure locator polynomial and the Forney syndromes are avoided. Thus for the VLSI implementation, the complexity and the processing time of this new decoding method are dramatically reduced. The method of the present invention takes advantage of certain desirable features of Euclid""s algorithm and of the BM algorithm.
According to the present invention, the errata locator polynomial and the errata evaluator polynomial for both erasures and errors are calculated simultaneously and there is no need to perform polynomial divisions within the reiteration process. Further, the need to compute the discrepancies and to perform the field element inversions, as required by the prior art, is eliminated. Thus, the duration of the processing time is substantially shortened.
More particularly, the present invention utilizes an iteration process similar to that of Euclid""s algorithm. According to the present invention, field element inversion computations are eliminated as well. According to the present invention, the errata evaluator polynomial is computed simultaneously with the errata locator polynomial. Further simplifying computation, polynomial swaps are avoided. Thus, the decoding method of the present invention for correcting both erasures and errors takes substantially less computations and time, as compared to contemporary algorithms such as Euclid""s algorithm and the BM algorithm. Furthermore, the present invention utilizes a simple multiplication process and a simple inversion process for simple and fast VLSI implementations.
The method for correcting erasures and errors in RS encoded data of the present invention can be practiced using either a computer or dedicated circuits, e.g., a VLSI implementation. These, as well as other advantages of the present invention will be more apparent from the following description and drawings. It is understood that changes in the specific structure shown and described may be made within the scope of the claims without departing from the spirit of the invention.